package dynamicPlanning;

/**
 * 完全背包
 * 有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。
 * 每件物品可以用无限次，求解怎么选择装入物品可以使物品总价值总和最大。 weight=[1,3,4] value=[15,20,30]
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class InfiniteBackpack {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.infiniteBackpack());
    }
    /**
     * 完全背包问题
     * 跟 01背包的区别在于，每一件物品是无限的
     * 我们依然设dp[i][j]为在0~i个物品中选择 放入到容量为j的背包中
     * 那么依旧就是两个选择
     * 将物品i不放入背包 dp[i][j] = dp[i-1][j];
     * 将k个物品i放入到背包 dp[i][j] = dp[i-1][j-weight[i]*k] + value[i]*k
     * 约束条件是  0 <= k <= j/weight[i]
     * */
    static class Solution{
        public int infiniteBackpack(){
            int[] value = {30, 20, 15};
            int[] weight = {4, 3, 1};
            int capacity = 4;
            int[][] dp = new int[value.length][capacity+1];

            // 初始化 当只可以选择第一个物品时
            for(int j = weight[0]; j <= capacity; j++){
                dp[0][j] = value[0];
            }

            for (int i = 1; i < value.length; i++) {
                for (int j = weight[i]; j <= capacity; j++) {
                    int num = j / weight[i];
                    for (int k = 1; k <= num; k++) {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]*k] + value[i]*k);
                    }
                }
            }
            return dp[value.length-1][capacity];
        }
    }

    /**
     * 最优解方法
     * dp[j] 表示背包容量为j时，其能够在0~i个物品选择的最大价值；
     *
     * 不放入物品i时 即dp[j] = dp[j-1]
     * 放入物品i时 即dp[j] = dp[j-weight[i]]+value[i]
     * */
    static class Solution1{
        public int infiniteBackpack(){
            int[] value = {20, 30, 15};
            int[] weight = {3, 4, 1};
            int capacity = 4;
            int[] dp = new int[capacity+1];

            for (int j = 1; j <= capacity; j++) {
                for (int i = 0; i < value.length; i++) {
                    if(j < weight[i]){
                        dp[j] = dp[j-1];
                    }else{
                        dp[j] = Math.max(dp[j-1],dp[j-weight[i]]+value[i]);
                    }
                }
            }
            return dp[capacity];
        }
    }
}
